package Chapter6;

import Chapter4.LinkedStack;
import Chapter4.SeqStack;
import Chapter4.Stack;

public class BinaryTree<T> {
    public BinaryNode<T> root;

    public BinaryTree() {
        this.root = new BinaryNode<T>();
    }

    /**
     * 6-21  BinaryTree(BinaryTree<T> bitree)        //深拷贝。两种算法：递归算法、使用栈
     *
     * @param
     */
    public BinaryTree(BinaryTree<T> bitree) {
        this.root = copy(bitree.root);
    }
    public BinaryNode<T> copy(BinaryNode<T> btnode) {
        if (btnode == null)
            return null;
        BinaryNode<T> p = new BinaryNode<T>(btnode.data);
        p.left = copy(btnode.left);
        p.right = copy(btnode.right);
        return p;
    }

//    public BinaryTree(BinaryTree<T> p) {
//        this();
//        LinkedStack<BinaryNode<T>> stack1 = new LinkedStack<BinaryNode<T>>(); //原树存储
//        LinkedStack<BinaryNode<T>> stack2 = new LinkedStack<BinaryNode<T>>(); //拷贝栈
//        BinaryNode<T> p1 = p.root;
//        BinaryNode<T> p2 = this.root;
//
//        if (p1.left == null && p1.right == null)
//            p2.data = p1.data;
//        else {
//            while (p1 != null || !stack1.isEmpty()) {
//                if (p1 != null) {
//                    p2.data = p1.data;
//                    stack1.push(p1); //结点进栈
//                    stack2.push(p2);
//                    p1 = p1.left;
//                    if (p1 != null) {  //p1结点不为空，创建新的结点
//                        BinaryNode<T> p3 = new BinaryNode<T>(p1.data);
//                        p2.left = p3;  //p2左结点为新的结点
//                        p2 = p2.left;  //p2指向左结点
//                    }
//                } else {
//                    p1 = stack1.pop();
//                    p1 = p1.right;
//                    p2 = stack2.pop();
//                    if (p1 != null) {  //p1结点不为空，创建新的结点
//                        BinaryNode<T> p3 = new BinaryNode<T>(p1.data);
//                        p2.right = p3;
//                        p2 = p2.right;
//                    }
//                }
//            }
//        }
//    }

    public boolean isEmpty() {
        return this.root == null;
    }

    /**
     * 插入x元素作为根结点，原根结点做x的左孩子
     *
     * @param x
     */
    public void insert(T x) {
        if (x != null)
            this.root = new BinaryNode<T>(x, this.root, null);
    }

    /**
     * 在中间结点处插入一个结点
     *
     * @param p
     * @param left
     * @param x
     * @return
     */
    public BinaryNode<T> insert(BinaryNode<T> p, boolean left, T x) {
        if (x == null || p == null)
            return null;
        if (left)
            return p.left = new BinaryNode<T>(x, p.left, null);
        return p.right = new BinaryNode<T>(x, null, p.right);
    }

    public void remove(BinaryNode<T> p, boolean left) {
        if (p != null) {
            if (left)
                p.left = null;
            else
                p.right = null;
        }
    }

    public void preorder(BinaryNode<T> p) {
        if (p != null) {
            System.out.print(p.data.toString() + " ");
            preorder(p.left);
            preorder(p.right);
        }
    }

    public void preorder() {
        preorder(this.root);
        System.out.println();
    }


    public void inorder(BinaryNode<T> p) {
        if (p != null) {
            inorder(p.left);
            System.out.print(p.data.toString() + " ");
            inorder(p.right);
        }
    }

    public void inorder() {
        inorder(this.root);
        System.out.println();
    }

    public void postorder(BinaryNode<T> p) {
        if (p != null) {
            postorder(p.left);
            postorder(p.right);
            System.out.print(p.data.toString() + " ");
        }
    }

    public void postorder() {
        postorder(this.root);
        System.out.println();
    }

    public String toString() {
        return "先根次序遍历二叉树：" + toString(this.root);
    }

    public String toString(BinaryNode<T> p) {
        if (p == null)
            return "^ ";
        return p.data.toString() + " " + toString(p.left) + toString(p.right);
    }

    public BinaryTree(T[] prelist) {
        this.root = create(prelist);
    }

    private int i = 0;

    private BinaryNode<T> create(T[] prelist) {
        BinaryNode<T> p = null;
        if (i < prelist.length) {
            T elem = prelist[i];
            i++;
            if (elem != null) {
                p = new BinaryNode<T>(elem);
                p.left = create(prelist);
                p.right = create(prelist);
            }
        }
        return p;
    }

    //
    public void remove2(BinaryNode<T> p, boolean left) {
        if (p != null) {   //先根次序遍历二叉树，输出空子树
            if (left) {
                System.out.println("删除子树：" + p.left.toString());
                p.left = null;
            } else {
                System.out.println("删除子树：" + p.right.toString());
                p.right = null;
            }
        }
    }

    //递归
    public boolean equals(BinaryNode<T> tree1, BinaryNode<T> tree2) {
        return (tree1 == null && tree2 == null) || tree1 != null && tree2 != null &&
                tree1.data.equals(tree2.data) &&
                (equals(tree1.left, tree2.left) && equals(tree1.right, tree2.right));
    }

    public void removeAll(BinaryTree<T> pattern) {
        removeAll(this.root, pattern.root);
    }

    public void removeAll(BinaryNode<T> p, BinaryNode<T> patternroot) {
        if (p != null) {
            if (equals(p.left, patternroot))
                remove(p, true);
            if (equals(p.right, patternroot))
                remove(p, false);
            removeAll(p.left, patternroot);
            removeAll(p.right, patternroot);
        }
    }

    //用栈
    public boolean equals2(BinaryNode<T> tree1, BinaryNode<T> tree2) {
        Stack<BinaryNode> s1 = new LinkedStack<BinaryNode>();
        Stack<BinaryNode> s2 = new LinkedStack<BinaryNode>();
        BinaryNode t1 = tree1, t2 = tree2;

        while ((t1 != null || !s1.isEmpty()) && (t2 != null || s2.isEmpty())) {
            if (t1 != null && t2 != null) {
                if (!t1.data.equals(t2.data))
                    return false;
                s1.push(t1);
                s2.push(t2);
                t1 = t1.left;
                t2 = t2.left;
            } else if (t1 == null && t2 == null) {
                t1 = s1.pop();
                t2 = s2.pop();
                t1 = t1.right;
                t2 = t2.right;
            } else
                return false;
        }
        if (t1 == null && t2 == null)
            return true;
        if (t1 == null || t2 == null)
            return false;
        return true;
    }

    public String toGenListString(BinaryNode<T> p) {
        if (p == null)
            return "^";
        if (p.left == null && p.right == null)
            return p.data.toString();
        return p.data.toString() + "(" + toGenListString(p.left) + "," + toGenListString(p.right) + ")";
    }

    public String toGenListString() {
        return "二叉树的广义表表示：" + toGenListString(this.root);
    }

    public void preorderTraverse() {
        LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                System.out.println(p.data + " ");
                stack.push(p);
                p = p.left;
            } else {
                System.out.println("^ ");
                p = stack.pop();
                p = p.right;
            }
        }
        System.out.println("^");
        /* //创建空栈
        LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        //p非空或栈非空时
        while(p!=null||!stack.isEmpty()){

            if(p!=null){

                System.out.print(p.data+" ");
                //p结点入栈
                stack.push(p);
                //访问左子树
                p = p.left;
            }else{

                //p指向出站结点
                p = stack.pop();
                p = p.right;
            }
        }
        System.out.println();*/
    }

    /**
     * 中根遍历，非递归算法
     */
    public void inorderTraverse() {
        LinkedStack<BinaryNode<T>> stack = new LinkedStack<>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                System.out.print(p.data + " ");
                p = p.right;
            }
        }
    }

    public void levelorder() {
        if (this.root == null)
            return;

    }

}
